leetcode/133. Clone Graph.c at master · vli02/leetcode · GitHub

Name: leetcode/133. Clone Graph.c at master · vli02/leetcode · GitHub
Rating: 4.5 (9099 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
/*
133. Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.


OJ's undirected graph serialization:


Nodes are labeled uniquely.


We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.


As an example, consider the serialized graph {0,1,2#1,2#2,2}.


The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.


Visually, the graph looks like the following:
 1
 / \
 / \
 0 --- 2
 / \
 \_/
*/

/**
 * #define NEIGHBORS_MAX_SIZE 100
 * struct UndirectedGraphNode {
 * int label;
 * struct UndirectedGraphNode *neighbors[NEIGHBORS_MAX_SIZE];
 * int neighborsCount;
 * };
 */
structUndirectedGraphNode*copy1node(structUndirectedGraphNode*graph,
structUndirectedGraphNode***srcpool,
structUndirectedGraphNode***dstpool,
int*sp, int*sz) {
structUndirectedGraphNode*node;
inti=0;

if (!graph) returnNULL;

while (i<*sp&& (*srcpool)[i] !=graph) {
i++;
 }
if (i==*sp) {
node=malloc(sizeof(structUndirectedGraphNode));
//assert(node);
node->label=graph->label;
if (*sp==*sz) {
*sz=*sz*2;
*srcpool=realloc(*srcpool, *sz*sizeof(structUndirectedGraphNode*));
*dstpool=realloc(*dstpool, *sz*sizeof(structUndirectedGraphNode*));
//assert(*srcpool && *dstpool && *stspool);
 }
 (*srcpool)[*sp] =graph;
 (*dstpool)[*sp] =node;
 (*sp) +=1;
i=0;
while (i<graph->neighborsCount) {
node->neighbors[i] =copy1node(graph->neighbors[i], srcpool, dstpool, sp, sz);
i++;
 }
node->neighborsCount=graph->neighborsCount;
 } else {
node= (*dstpool)[i];
 }

returnnode;
}

structUndirectedGraphNode*cloneGraph(structUndirectedGraphNode*graph) {
structUndirectedGraphNode**srcpool, **dstpool, *node;
intsp=0, sz=100;

srcpool=malloc(sz*sizeof(structUndirectedGraphNode*));
dstpool=malloc(sz*sizeof(structUndirectedGraphNode*));
//assert(srcpool && dstpool && stspool);

node=copy1node(graph, &srcpool, &dstpool, &sp, &sz);

free(srcpool); free(dstpool);

returnnode;
}


/*
Difficulty:Medium
Total Accepted:116.4K
Total Submissions:463.8K


Companies Pocket Gems Google Uber Facebook
Related Topics Depth-first Search Breadth-first Search Graph
Similar Questions


 Copy List with Random Pointer
*/